package main

import (
	"fmt"
	"math/rand"
	"time"
)

/*
只要了解好荷兰国旗问题，就能理解快速排序递归的快速排序的难点就在理解随机数对于快速排序的作用
*/
func main() {
	arr := []int{2, 4, 5, 67, 4, 3, 25, 6, 8, 4}
	quickSort3(arr)
	fmt.Println(arr)
}
func quickSort3(arr []int) {
	if arr == nil && len(arr) < 1 {
		return
	}
	process3(arr, 0, len(arr)-1)
}
func process3(arr []int, L, R int) {
	if L == R || L > R { //当L==R时说明当前数组只有一个元素了就没必要排序了
		return
	}
	rand.Seed(time.Now().UnixNano())
	SwapIndex := L + rand.Intn(R-L+1)
	fmt.Println(arr)
	arr[SwapIndex], arr[R] = arr[R], arr[SwapIndex] //第三版和第二版的区别就是将第二版一直放在末尾的标准数跟前面范围内的随机的数进行交换
	fmt.Println(arr, SwapIndex, R)
	ints := sorttt(arr, L, R) //返回的是标准数的区间也就是不可能再动的区间
	fmt.Println(ints, L, R)
	process3(arr, L, ints[0]-1) //结合标准数区间和当前LR的值就可以得出左右两边递归的范围
	process3(arr, ints[1]+1, R)
}
func sorttt(arr []int, L, R int) []int {
	if L > R {
		return []int{-1, -1}
	}
	if L == R {
		return []int{L, R}
	}
	less := L - 1
	more := R //more默认是最后一个数的后面的下标但是最后一个数是用来比较的标准数所以more现在的位置就相当于要排序范围的最后
	index := L
	for index < more {
		if arr[index] < arr[R] {
			less++
			arr[index], arr[less] = arr[less], arr[index]
			index++
		} else if arr[index] == arr[R] {
			index++
		} else if arr[index] > arr[R] {
			more--
			arr[index], arr[more] = arr[more], arr[index] //这里index不+1是因为和大于标准数的数换完后的那个数还没经过比较所以不index++
		}
	}
	arr[R], arr[more] = arr[more], arr[R] //这步是交换标准数和第一个最大数保证排完的数组是有序的
	return []int{less + 1, more}          //因为标准数和最大数换了后当前more的位置就是标准数所以不需要减一，
	// less本来指向的就是标准数的前一个位置所以为了正确标注出标准数的区间要+1

}
